Virtual memory is a memory system used to increase the effectiveness of a computer's physical memory. Virtual memory maps the user's logical addresses to physical addresses, so parts of a program may reside at physical addresses that differ from the logical addresses.
In practice, the logical-address space of many computers is much larger than their physical-address space. For example, if a byte-addressed computer uses a 32-bit address, its logical-address space has 2.sup.32 memory locations, which is 4 GB. Few computers have that much physical memory (perhaps until recently) though many of them use 32-bit addresses. Consequently, until the advent of virtual memory, either the operating system restricted the size of a program to the size of physical memory, or a programmer had to use overlays or similar techniques to reduce the program's maximum physical size.
In a virtual-memory system, the operating system loads only part of a program in main memory at one time. When the active part of the program requests a memory reference, the CPU resolves the effective address exactly as it would if the computer did not have virtual memory. However, it does not send the effective address directly to its main-memory system. Instead, it sends it to a memory map, which is part of the virtual-memory hardware. The memory map is a system that translates virtual addresses into physical addresses. A good overview of virtual memory techniques appears in R. Baron and L. Higbie, Computer Architecture, Chapter 4 (Addison-Wesley Publishing Company, 1992).
Paging and segmentation are examples of techniques for mapping effective addresses into physical addresses. In a paging system, the virtual memory hardware divides logical addresses into two parts, page number and a word offset within the page. This is done by partitioning the bits of the addresses: the high order bits form the page number and the low order bits form the offset. When the system loads a page into memory, it always places the page beginning at a page boundary. The units of physical memory that hold pages are called page frames.
In a demand-page virtual-memory system, the memory map is called a page map. As part of the page map, the operating system maintains a page table. A page table consists of a number of page table entries, each holding information about a specific page. The virtual page number thus serves as an offset into the page table. A typical page-table entry includes a validity bit, a dirty bit, protection bits, and the page-frame number for the page.
Most paging systems keep their page tables in main memory, and the hardware may have a page table base register that points to the page table in memory. When the page table is in main memory, each main-memory access potentially requires the overhead of a second memory access: the addressing hardware must consult the page table to get the page-frame number for the memory reference. To avoid (minimize) the additional overhead, some hardware systems maintain, as part of the page map, a small cache memory called a translation look-aside buffer (TLB), which holds essentially the same information as part of the page table. In addition, it holds the virtual-page number so it can map the virtual page number to the corresponding page frame number. In general, a TLB holds entries only for the most recently accessed pages.
The effective address is the address the CPU generates to reference an instruction or variable in memory using the instruction-provided addressing modes such as base displacement and indexing but not using the address-translation mechanisms of virtual memory. This is usually the same as the compiler's logical address but not the same as the computer's physical address.
In the prior art, an effective address comprises at least two parts, which we will call the explicit address and the indirect address. A portion of the explicit address, to be called the index, serves as an index into a space register file. The contents of the space register file form the indirect address.
The effective address is formed by a concatenation of the indirect address bits and the explicit address bits, and may include all, some, or none of the index bits. The Most of the bits of the effective address (i.e., not the page offset bits) are classically used to access the translation look-aside buffer (TLB), which stores a page frame number or segment-base address (in a segmented system) which in turn forms part of the physical address. The TLB entry is said to match if its value is equal to the effective address used to access the TLB.
Conventional mechanisms do not begin the TLB access until the space register has been accessed and the full effective address is thus available. This serial access of the space register file and then the TLB increases the critical TLB path and therefore slows the overall memory system performance. In addition, if the TLB path is the critical stage in a pipelined computer design, the operating frequency of the design can be degraded as well, resulting in a degradation in overall system performance. The need remains, therefore, for improved methods and apparatus for implementing virtual memory architectures.